package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 图的广度优先遍历实现
 *
 * @author initcap
 * @date Created in 7/31/19 9:54 AM.
 */
public class SingleSourcePath {

    private Graph<Integer, Double> graph;
    private boolean[] visited;
    private int[] pre;
    private int s;

    public SingleSourcePath(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        visited = new boolean[graph.nodeSize()];
        pre = new int[graph.nodeSize()];
        for (int i = 0; i < graph.nodeSize(); i++) {
            pre[i] = -1;
        }
        bfs(s);
    }

    public static void main(String[] args) {
        Graph graph = new SparseGraph("algorithm/testG10.txt", false);
        SingleSourcePath singleSourcePath = new SingleSourcePath(graph, 0);
        singleSourcePath.showPath(6);

    }

    private void bfs(int s) {
        Queue<Integer> queue = new LinkedList();
        queue.add(s);
        visited[s] = true;
        pre[s] = s;
        while (!queue.isEmpty()) {
            int v = queue.poll();

            for (int w : graph.adj(v)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                    pre[w] = v;
                }
            }

        }
    }

    /**
     * 查询从s点到w点是否有路径
     *
     * @param w
     * @return
     */
    public boolean hasPath(int w) {
        graph.validateVertex(w, graph.nodeSize());
        return visited[w];
    }

    public Iterable<Integer> path(int w) {
        List<Integer> res = new ArrayList<>();
        if (!hasPath(w)) {
            return res;
        }

        int cur = w;
        while (cur != s) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    /**
     * 打印出从s点到w点的路径
     *
     * @param w
     */
    public void showPath(int w) {

        assert hasPath(w);

        List<Integer> vec = (List) path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.get(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

}
